/**
 * 插入排序
 *
 * 依次跟已经排序好的数组比较，交换位置，直到找到真正的位置。交换的次数较多
 */
public class InsertionSort extends TemplateSort {
    @Override
    void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) {
            // 将 a[i] 插入到 a[i-1],a[i-2],a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
                exch(a, j, j-1);

                // 显示排序过程及交换次数
//                show(a);
            }
        }
    }

    public static void main(String[] args) {
        TemplateSort templateSort = new InsertionSort();

        Comparable[] data = templateSort.createInt(0, 1000, 300);

        templateSort.run(data);
    }
}
